package leetcode.medium.limit50;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yaoyao1.liu@zhaopin.com.cn
 * @since 2022-11-08 17:36
 **/
public class No46 {
    public static void main(String[] args) {
        No46 no46 = new No46();

        List<List<Integer>> permute = no46.permute(new int[]{1, 2, 3});
        System.out.println(permute);
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        if (length == 0) {
            return result;
        }
        boolean[] used = new boolean[length];
        deal(result, 0, length, nums, new ArrayList<>(), used);
        return result;
    }

    public void deal(List<List<Integer>> result, int index, int length, int[] nums, List<Integer> one, boolean[] used) {
        if (index == length) {
            result.add(new ArrayList<>(one));
            return;
        }
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (!used[i]) {
                one.add(num);
                used[i] = true;
                deal(result, index + 1, length, nums, one, used);
                used[i] = false;
                one.remove(one.size() - 1);
            }
        }
    }

}
